package com.stable;

/**
 * 
 * @author Bhattacharjee, Bhatia
 * COP 5537, Network optimization
 * Project Code: Stable Marriage Program
 * 
 * This class will generate the Problem matrix with 
 * incomplete and Tie preference list.
 * 
 */


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class LocalSearchSM {

	private int n;
	
	ArrayList<ArrayList<LinkedList<Integer>>> lsMPref = new ArrayList<ArrayList<LinkedList<Integer>>>();
	ArrayList<ArrayList<LinkedList<Integer>>> lsWPref = new ArrayList<ArrayList<LinkedList<Integer>>>();

	private double p1 = 0.0;// probability for incompleteness
	private double p2 = 0.0;// probability for Ties
	/*
	 * private int[] randomMarriage; 
	 * private int[] rmPrefMan; 
	 * private int[]rmPrefWoman; 
	 * private int evl_function = 0; 
	 * private HashMap<Integer,Integer> blockingPairs = new HashMap<Integer, Integer>();
	 */
	final int NOT_ENGAGED = -1;
	private boolean Man;
	private Random rand = new Random();

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		LocalSearchSM sm = new LocalSearchSM(5, 0.3, 0.3, true);

		int[] randomMarriage = new int[sm.getN()];
		int[] rmPrefMan = new int[sm.getN()];
		int[] rmPrefWoman = new int[sm.getN()];
		HashMap<Integer,Integer> blockingPairs = new HashMap<Integer, Integer>();
		
		

		randomMarriage = sm.createRandomMarriage(sm.isMan());
		sm.printRandomMarriage(randomMarriage);
		
		rmPrefMan = sm.findPrefofRM(randomMarriage, true);//true for man
		sm.printPrefRM(rmPrefMan, true);
		
		rmPrefWoman = sm.findPrefofRM(randomMarriage, false);
		sm.printPrefRM(rmPrefWoman, false);
		
		
		System.out.println("No. of singles in Random Marriage: "
				+ sm.findSingleRM(randomMarriage));
		
		
		blockingPairs = sm.findBlockingPair(randomMarriage,rmPrefMan,rmPrefWoman );
		sm.printBlockinPairs(blockingPairs);
		sm.findEvl_Fun_Value(blockingPairs, randomMarriage);

	}

	/**
	 * @param n size of the man and women, we are taking equal number of man and woman
	 * @param p1, probability for creating incompleteness of preferences
	 * @param p2, probability for creating Ties of preferences
	 */
	public LocalSearchSM(int n, double p1, double p2, boolean pref) {
		// super();
		this.n = n;
		this.p1 = p1;
		this.p2 = p2;
		this.Man = pref;
		LocalSearchPG sm = new LocalSearchPG(n, p1, p2);
		this.lsMPref = sm.createPreferenceList_TI(true);
		this.lsWPref = sm.createPreferenceList_TI(false);
	}

	/**
	 * 
	 * @param blockingPairs, all blocking pairs
	 * @param randomMarriage, random marriage
	 * @return will return Evaluation function value = no. of blockingpair + no. of single in marriage
	 */
	public int findEvl_Fun_Value(HashMap<Integer, Integer> blockingPairs, int[] randomMarriage) { // f(M) = nbp(M) + ns(M) // nbp = no of
										// blocking pairs // ns = no. of singles
		int count = 0;								// int count = 0;
		count = findSingleRM(randomMarriage);
		count = count + blockingPairs.size();
		
		System.out.println("evalFun(M): " + count);
		return count;
	}
	
/**
 * 
 * @param blockingPairs, print blocking pairs
 */
	public void printBlockinPairs(HashMap<Integer,Integer> blockingPairs)

	{
		System.out.println("Blocking pairs");
		if (Man) {
			System.out.println("m : w");
			for (Integer p : blockingPairs.keySet()) {
				System.out.println(p + " : " + blockingPairs.get(p));

			}
		} else {
			System.out.println("w : m");
			for (Integer p : blockingPairs.keySet()) {
				System.out.println(p + " : " + blockingPairs.get(p));

			}
		}
	}
	 
	/**
	 * 
	 * @param prefList, print prefence of male or female as goverened random marriage.
	 * @param Male
	 */
	public void printPrefRM(int[] prefList, boolean Male) {
		if(Male)
			System.out.println("Man preference from Random Marriage");
		else
			System.out.println("Woman preference from Random Marriage");
		
		for (int i = 0; i < prefList.length; i++) {
			System.out.println(prefList[i]);
		}
	}

	/**
	 * 
	 * @param randomMarriage
	 * @return return number of single in random marriage
	 */
	public int findSingleRM(int[] randomMarriage) {
		int count = 0;
		int[] currentWoman = new int[n];
		int[] currentMan = new int[n];
		for (int i = 0; i < n; i++) {
			currentWoman[i] = NOT_ENGAGED;
			currentMan[i] = NOT_ENGAGED;
		}

		for (int i = 0; i < n; i++) {
			if (randomMarriage[i] != -1) {
				currentWoman[i] = 0;
				currentMan[randomMarriage[i]] = 0;
			}

		}
		for (int i = 0; i < n; i++) {
			if (currentMan[i] == -1) {
				count++;
			}
			if ((currentWoman[i] == -1)) {
				count++;
			}
		}

		return count;
	}
	
	/**
	 * 
	 * @param randomMarriage
	 * @param rmPrefMan
	 * @param rmPrefWoman
	 * @return	return all the blocking pair w.r.t. random marriage
	 */

	public HashMap<Integer, Integer> findBlockingPair(int[] randomMarriage, int[] rmPrefMan, int[] rmPrefWoman) {
		HashMap<Integer, Integer> blockingPairs = new HashMap<Integer, Integer>();

		if (Man) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (j == randomMarriage[i]) {
						continue;
					}
					int isMpreW = preference(i, j, true);
					int isWpreM = preference(i, j, false);

					if ((isMpreW != -1) && (isWpreM != -1)) {
						if ((isPreference(i, true, rmPrefMan) == NOT_ENGAGED)
								|| (isMpreW < isPreference(i, true, rmPrefMan))) {
							if ((isPreference(j, false, rmPrefWoman) == NOT_ENGAGED)
									|| (isWpreM < isPreference(j, false,
											rmPrefWoman))) {
								blockingPairs.put(i, j);
							}
						}
					}

				}
			}
		} else {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (j == randomMarriage[i]) {
						continue;
					}
					int isMpreW = preference(j, i, true);
					int isWpreM = preference(j, i, false);

					if ((isMpreW != -1) && (isWpreM != -1)) {
						if ((isPreference(i, false, rmPrefWoman) == NOT_ENGAGED)
								|| (isWpreM < isPreference(i, false,
										rmPrefWoman))) {
							if ((isPreference(j, true, rmPrefMan) == NOT_ENGAGED)
									|| (isMpreW < isPreference(j, true,
											rmPrefMan))) {
								blockingPairs.put(i, j);
							}
						}
					}

				}
			}
		}
		return blockingPairs;

	}

	/**
	 * 
	 * @param a
	 * @param Male
	 * @param prefMan
	 * @return return the b opposite of "a" in married couple "a-b".
	 */
	public int isPreference(int a, boolean Male, int[] prefMan) {
		if (Male) {
			if (prefMan[a] == NOT_ENGAGED)
				return NOT_ENGAGED;
			else
				return prefMan[a];
		} else {
			if (prefMan[a] == NOT_ENGAGED)
				return NOT_ENGAGED;
			else
				return prefMan[a];
		}

	}

	/**
	 * 
	 * @param m
	 * @param w
	 * @param Male
	 * @return return the position of preference of opposite gender.
	 */
	public int preference(int m, int w, boolean Male) {
		if (Male) {

			int k = lsMPref.get(m).size(); // Total no. of preference level
											// for
											// particular Man
			for (int j = 0; j < k; j++) { // Going through no. of women in
											// each
											// preference level.
				int l = lsMPref.get(m).get(j).size(); // Total no. of women
														// for
														// particular
														// preference
														// level
				for (int l2 = 0; l2 < l; l2++) {
					if (lsMPref.get(m).get(j).get(l2) == w) {
						return j;

					}
				}
			}
		} else {
			int k = lsWPref.get(w).size(); // Total no. of preference level
			// for
			// particular Man
			for (int j = 0; j < k; j++) { // Going through no. of women in
				// each
				// preference level.
				int l = lsWPref.get(w).get(j).size(); // Total no. of women
				// for
				// particular
				// preference
				// level
				for (int l2 = 0; l2 < l; l2++) {
					if (m == lsWPref.get(w).get(j).get(l2)) {
						return j;

					}
				}
			}
		}

		return -1;
	}
	
	/**
	 * 
	 * @param randomMarriage
	 * print the random marriage
	 * 
	 */

	public void printRandomMarriage(int[] randomMarriage) {
		System.out.println("random Marriage");

		if (Man)
			System.out.println("m : w");
		else
			System.out.println("w : m");

		for (int i = 0; i < randomMarriage.length; i++) {
			System.out.println(i + " : " + randomMarriage[i]);

		}

	}

	/**
	 * 
	 * @param M
	 *            , true for random marriage according to manPref and false for
	 *            random marriage according to womanPref
	 * @return
	 * return random marriage.
	 */

	public int[] createRandomMarriage(boolean man) {
		int[] currentWoman = new int[n];
		int[] currentMan = new int[n];
		int[] randomMarriage = new int[n];

		for (int i = 0; i < n; i++) {
			currentWoman[i] = NOT_ENGAGED;
			currentMan[i] = NOT_ENGAGED;
			randomMarriage[i] = NOT_ENGAGED;
		}

		for (int i = 0; i < n; i++) {
			if (man) {
				List<Integer> womenList = new ArrayList<Integer>();
				int k = lsMPref.get(i).size(); // Total no. of preference for
												// particular Man
				for (int j = 0; j < k; j++) { // Going through no. of women in
												// each preference level.
					int l = lsMPref.get(i).get(j).size(); // Total no. of women
															// for particular
															// preference
					for (int l2 = 0; l2 < l; l2++) {
						womenList.add(lsMPref.get(i).get(j).get(l2));
					}
				}
				Collections.shuffle(womenList);

				for (Integer m1 : womenList) {
					if (currentWoman[m1] == NOT_ENGAGED) {
						if (preference(i, m1, false) != -1){
							randomMarriage[i] = m1;
							currentWoman[m1] = i;
							break;
						}
						
					}
				}

			} else {
				List<Integer> menList = new ArrayList<Integer>();
				int k = lsWPref.get(i).size();// Total no. of preference for
												// particular Woman
				for (int j = 0; j < k; j++) {// Going through no. of men in each
												// preference level.
					int l = lsWPref.get(i).get(j).size();// Total no. of men for
															// particular
															// preference
					for (int l2 = 0; l2 < l; l2++) {
						menList.add(lsWPref.get(i).get(j).get(l2));
					}
				}
				Collections.shuffle(menList);

				for (Integer m : menList) {
					if (currentMan[m] == NOT_ENGAGED) {
						if (preference(m, i, true) != -1){
							
						}
						randomMarriage[i] = m;
						currentMan[m] = i;
						break;
					}
				}

			}
		}

		return randomMarriage;

	}

	
	
	public int[] findPrefofRM(int[] randomMarriage, boolean checkforMan) {
		int[] prefList = new int[n];
		for (int i = 0; i < n; i++) {
			prefList[i] = NOT_ENGAGED;
		}
		for (int i = 0; i < n; i++) {
			if (Man) {
				if (checkforMan) {
					
						

						if (randomMarriage[i] == NOT_ENGAGED) {
							continue;
						}
						int k = lsMPref.get(i).size(); // Total no. of
														// preference level
														// for
														// particular Man
						for (int j = 0; j < k; j++) { // Going through no. of
														// women in
														// each
														// preference level.
							int l = lsMPref.get(i).get(j).size(); // Total no.
																	// of women
																	// for
																	// particular
																	// preference
																	// level
							for (int l2 = 0; l2 < l; l2++) {
								if (randomMarriage[i] == lsMPref.get(i).get(j).get(l2)) {
									prefList[i] = j;

								}
							}
						}
					
				} else {
					
						

						if (randomMarriage[i] == NOT_ENGAGED) {
							continue;
						}
						int k = lsWPref.get(randomMarriage[i]).size();// Total no.
																	// of
						// preference
						// for
						// particular Woman
						for (int j = 0; j < k; j++) {// Going through no. of men
														// in each
						// preference level.
							int l = lsWPref.get(randomMarriage[i]).get(j).size();// Total
							// no. of men for particular preference
							for (int l2 = 0; l2 < l; l2++) {
								if (i == lsWPref.get(randomMarriage[i]).get(j).get(l2)) {
									prefList[randomMarriage[i]] = j;
								}
							}
						}

					
				}
			}

			else {
				if (checkforMan) {
					
						// System.out.println(randomMarriage[i]);

						if (randomMarriage[i] == NOT_ENGAGED) {
							continue;
						}
						int k = lsMPref.get(randomMarriage[i]).size(); // Total no. of
														// preference level
														// for
														// particular Man
						for (int j = 0; j < k; j++) { // Going through no. of
														// women in
														// each
														// preference level.
							int l = lsMPref.get(randomMarriage[i]).get(j).size(); // Total no.
																	// of women
																	// for
																	// particular
																	// preference
																	// level
							for (int l2 = 0; l2 < l; l2++) {
								if (i == lsMPref.get(randomMarriage[i]).get(j).get(l2)) {
									prefList[randomMarriage[i]] = j;

								}
							}
						}
					
				} else {
					

						if (randomMarriage[i] == NOT_ENGAGED) {
							
							continue;
						}
						int k = lsWPref.get(i).size();// Total no.
																	// of
						// preference
						// for
						// particular Woman
						for (int j = 0; j < k; j++) {// Going through no. of men
														// in each
						// preference level.
							int l = lsWPref.get(i).get(j).size();// Total no. of men for particular preference
							for (int l2 = 0; l2 < l; l2++) {
								if (randomMarriage[i] == lsWPref.get(i).get(j).get(l2)) {
									prefList[i] = j;
								}
							}
						}

					
				}
			}
		}

		return prefList;
	}

	/*
	 * public int find_opposite(int agent, int[] randomMarriage) {
	 * 
	 * for (int i = 0; i < randomMarriage.length; i++) { if (randomMarriage[i]
	 * == agent) { return i; } }
	 * 
	 * return -1;
	 * 
	 * }
	 */

	/**
	 * @return the lsMPref
	 */
	public ArrayList<ArrayList<LinkedList<Integer>>> getLsMPref() {
		return lsMPref;
	}

	/**
	 * @param lsMPref
	 *            the lsMPref to set
	 */
	public void setLsMPref(ArrayList<ArrayList<LinkedList<Integer>>> lsMPref) {
		this.lsMPref = lsMPref;
	}

	/**
	 * @return the lsWPref
	 */
	public ArrayList<ArrayList<LinkedList<Integer>>> getLsWPref() {
		return lsWPref;
	}

	/**
	 * @param lsWPref
	 *            the lsWPref to set
	 */
	public void setLsWPref(ArrayList<ArrayList<LinkedList<Integer>>> lsWPref) {
		this.lsWPref = lsWPref;
	}

	/**
	 * @return the n
	 */
	public int getN() {
		return n;
	}

	/**
	 * @param n
	 *            the n to set
	 */
	public void setN(int n) {
		this.n = n;
	}

	/**
	 * @return the man
	 */
	public boolean isMan() {
		return Man;
	}

	/**
	 * @param man
	 *            the man to set
	 */
	public void setMan(boolean man) {
		Man = man;
	}

}
